/*
 * @lc app=leetcode.cn id=22 lang=golang
 *
 * [22] 括号生成
 */

// 2. 优雅的递归
// 直接生成符合条件的
// @lc code=start
func generateParenthesis(n int) (ans []string) {
	var generate func(left, right int, str string)
	generate = func(left, right int, str string) {
		if left == n && left == right {
			ans = append(ans, str)
			return
		}
		if left < n {
			generate(left+1, right, str+"(")
		}

		if right < left {
			generate(left, right+1, str+")")
		}
	}
	generate(0, 0, "")
	return
}

// @lc code=end

// 1. 暴力递归
// 拿到所有的组合，再去筛选符合条件的
// @lc code=start
func generateParenthesis(n int) (ans []string) {
	var generate func(num int, str string)
	generate = func(num int, str string) {
		if num == 2*n {
			if valid(str) {
				ans = append(ans, str)
			}
			return
		}
		generate(num+1, str+"(")
		generate(num+1, str+")")
	}
	generate(0, "")
	return
}

func valid(str string) bool {
	balance := 0
	for i := 0; i < len(str); i++ {
		if str[i] == '(' {
			balance++
		} else {
			balance--
		}
		if balance < 0 {
			return false
		}
	}
	return balance == 0
}

// @lc code=end

